1. Field of the Invention
The present invention relates to a Viterbi decoding apparatus for use in satellite broadcasting.
2. Description of the Related Art
As one of the decoding methods of a convolutional code, there is known a Viterbi decoding method.
The Viterbi decoding method is a maximum likelihood decoding method of a convolutional code. An error correction is achieved by selecting the sequence closest to the received code sequence (which is called the maximum likelihood path) out of the code sequences which can be generated by an encoder on the transmission side.
The method for selecting the maximum likelihood path is not one that confirms it by comparing all of the paths, but, in principle, is one that obtains the Hamming distances between all of the code sequences generated on the transmission side and the received code sequence and selects the smallest one of them (i.e.,-that has the maximum likelihood) and, thereafter, checks only the paths necessary for decoding (surviving paths). If a path of a sufficient length is taken, the ends (bases) of the surviving paths meet one another at the same value and, hence, it is known that the same value is decoded whichever surviving path is taken, if it is traced back.
Therefore, by determining a path length that will not produce a high error rate, the data at the point of time traced back through the path of that length can be used as the decoded data.
FIG. 5 is a block diagram showing an example of a Viterbi decoding apparatus using such a Viterbi decoding method as described above.
The Viterbi decoding apparatus shown in FIG. 5 comprises a branch metric calculation circuit 101, an ACS add-compare-select circuit 102, a normalizaion circuit 103, a state metric storage circuit 104, a path memory circuit 105, and a maximum likelihood sequence decision circuit 106, and when data output from the transmission side (input data) is input to this circuit, the sequence closest to the received code sequence is selected from the code sequences which can be generated by the encoder on the transmission side and the decoded data is generated according to the selected content.
The branch metric calculation circuit 101, when the input data is input, calculates the branch metric of the input data (the Hamming distance between the received code and the path) and supplies the result of calculation (branch metric) to the ACS circuit 102.
The ACS circuit 102, according to the branch metric supplied from the branch metric calculation circuit 101 and a state metric (accumulation) supplied from the state metric storage circuit 104 adds up, with respect to each of two paths meeting each other at a state, the branch metric for the path and the accumulation of the branch metrics up to the preceding stage (state metric), compares the sums with each other, and selects, according to the results of comparison, the one being higher in likelihood, and then, supplies the content or the selection to the path memory circuit 105 and, also, supplies the sum being higher in likelihood to the normalization circuit 103 as a newly obtained accumulation (state metric).
When, in this case, the constraint length is "7" and the number of states is "64" the Hamming distance between the received code and the path (branch metric) and the accumulation of the branch metrics up to the preceding stage (state metric) with respect to each of the two paths meeting each other at a state are added up for each time slot as shown in the transition diagram shown in FIG. 6 and the results of addition are compared with each other and, according to the results of comparison, the one being higher in likelihood is selected.
The normalization circuit 103 normalizes the state metric output from the ACS circuit 102 to a value within a preset range and supplies this normalized state metric to the state metric storage circuit 104.
The state metric storage circuit 104 stores the normalized state metric supplied from the normalization circuit 103 and, at the same time, feeds back each state metric stored therein to the ACS circuit 102.
The path memory circuit 105 stores the selected content output from the ACS circuit 102 and supplies this selected content to the maximum likelihood sequence decision circuit 106.
The maximum likelihood sequence decision circuit 106, according to the selected content stored in the path memory circuit 105 and the stored content in the state metric storage circuit 104, determines the path having the maximum likelihood to generate decoded data and outputs the decoded data.
Since, in the Viterbi decoding apparatus as described above, the value of the state metric in the preceding decoding stage is added in the current decoding stage, circuits from the state metric storage circuit 104 are connected to the adder (not shown) in the ACS circuit 102 in the form of a loop.
Since the computation in the loop must be performed within the information rate, it is necessary, in order to increase the information rate, to lower the maximum value of the time required in the loop portion.
In this case, the circuits having the greatest influence on the operation speed of those within the loop are the ACS circuit 102, which adds up the Hamming distance between the received code and the path (branch metric) and the accumulation of the branch metrics up to the preceding stage (state metric) for each of the two paths meeting each other at a state, compares the sums with each other, and selects the one being higher in likelihood, and the normalization circuit 103, which normalizes the state metric output from the ACS circuit 102.
However, the ACS circuit 102 of the conventional type used in such a Viterbi decoding apparatus as described above, when outputting path selection signals S.sub.(t), S.sub.(t+1), . . . , which correspond to transition information of the paths, for each time slot as shown in FIG. 7, requires the time T.sub.T, as the computation time, expressed as EQU T.sub.T =T.sub.A +T.sub.C +T.sub.S, (1)
where
T.sub.A : time required for addition, PA1 T.sub.C : time required for comparison, PA1 T.sub.S : time required for selection.
Further, in order to increase the information rate by reducing this time, T.sub.T, very precise synchronous clocking must be achieved.
Therefore, if the information rate is increased with the conventional circuit configuration used, such a problem in the circuit operation arises in that the transition time easily shifts and control of the clocking becomes difficult.
Further, a certain length of processing time for normalization is required in the normalization circuit 103 because various processes are to be performed therein such as making a decision on normalization, setting the normalization timing, and performing the normalization process.
Therefore, the information rate cannot be increased unless the processing speed in the loop portion is reduced by shortening the above described processing time.
Further, in the conventional Viterbi decoding apparatus, especially the apparatus that treats a punctured code with a large constraint length and has a large circuit scale, it is required that the number of bits of the state metric is reduced as much as possible and the circuit scale is made small.
In such a Viterbi decoding apparatus, the value of the state metric selected by the ACS circuit 102 continually increases with time because it is the sum total of the branch metrics of the surviving paths. Hence, it is arranged such that the value of the state metric selected by the ACS circuit 102 is normalized under a predetermined condition by the normalization circuit 103 provided in the stage subsequent to the ACS circuit 102.
What is most preferable as the method of normalization at this time is to subtract, from all of the state metrics, the minimum value of them, but if the values of the state metrics output from the ACS circuit 102 are normalized by such a method, the processing speed in the entire loop becomes low.
Accordingly, with the conventional circuit configuration, the maximum operation speed is determined by the computation speed in the loop in one time slot, and therefore, in the case where the constraint length is "7" and the encode rate is "7/8", 25 Mbps is the attainable upper limit by the technology level at present.
Therefore, there has been a problem that an information rate of 30 Mbps or above as required in decoding a convolutional code used in HDTV broadcasting or the like cannot be processed.